﻿// 901 快速幂练习.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
/*
http://oj.daimayuan.top/course/22/problem/1043

给你两个数 a和 n，你需要求出 a的 n次方模 109+7的值。

输入格式
一行两个整数 a和 n。

输出格式
一个正整数表示答案。

样例输入
5 10000
样例输出
378321089
数据范围
对于 100%的数据，保证 1≤a,n≤109
*/

#include <iostream>

using namespace std;

const long long MOD = 1e9 + 7;
int a,n;

long long quickmi(long long a, long long b) {
	long long res = 1;
	while (b) {
		if (b & 1) {
			res = res * a; 
			res %= MOD;
		}
		b >>= 1;
		a = a * a; a %= MOD;
	}

	return res;
}

int main()
{
	cin >> a >> n;
	cout << quickmi(a, n);

	return 0;
}

 